package leetcode;

/**
 * 题目：最长回文子串
 * 链接：https://leetcode.cn/problems/longest-palindromic-substring/description/
 * ?envType=problem-list-v2&envId=dynamic-programming&
 * 示例 1：
 *
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 *
 * 输入：s = "cbbd"
 * 输出："bb"
 */
public class LongestPalindrome2 {

    public static void main(String[] args) {
        String s = "abac";
        String s1 = longestPalindromeSubseq(s);
        System.out.println(s1);
    }
    public static boolean isPalindromic(String s) {
        int left=0;
        int right=s.length()-1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    // 暴力解法
    public static String longestPalindromeSubseq(String s) {
        String ans = "";
        int max = 0;
        int len = s.length();
        for (int i = 0; i < len; i++)
            for (int j = i + 1; j <= len; j++) {
                String test = s.substring(i, j);
                if (isPalindromic(test) && test.length() > max) {
                    ans = test;
                    max = Math.max(max, ans.length());
                }
            }
        return ans;
    }
}
